package algorithm;
import java.util.ArrayList;

import structure.*;

public class algorithm {

	public algorithm(){
		
	}
	
	//elimina le e-production
	public static grammar eliminateEpsilonProduction(grammar g){

		System.out.println("----------------------------------------------");
		System.out.println("Starting of eliminateEProduction procedure.");
		System.out.println("----------------------------------------------");
		
		grammar gg;
		
		if(utility.isThereEproduction(g.getAllProduction()) == true){
			
			
			//Step 1
			//costruisco l'insieme dei nullabili
			ArrayList<String> nullable= utility.getNullable(g.getAllProduction());
			System.out.println("Step 1 complete");
			
			//Step 2
			//se S è nullabile aggiungi la produzione S->e
			boolean addSproduction= false;
			if(nullable.contains(g.getS())) addSproduction= true;
			System.out.println("Step 2 complete");
			
			//Step 3
			//rimpiazza le produzioni
			/*
			 * Se P->aQb e Q è nullable allora
			 * aggiungi P->ab ed elimina Q->e
			 */
			ArrayList<production> productions= g.getAllProduction();
			
			for(production p : productions){
				
				ArrayList<String> rightside= p.getRightSide();
				ArrayList<String> rightsideNew= new ArrayList<String>();
				
				for(String s : rightside){
					//se di lunghezza 1 la aggiungo al nuovo rightside
					if(s.length() == 1 && !rightsideNew.contains(s) && !s.equals("e")){
						rightsideNew.add(s);
					}
					else if(s.length() > 1 && !rightsideNew.contains(s)){
						
						rightsideNew.add(s);
						char[] tmpC= s.toCharArray();
						ArrayList<Integer> position= new ArrayList<Integer>();
						
						//trovo le posizioni dei nullabili
						for(int i=0; i<tmpC.length; i++){
							
							if(nullable.contains(Character.toString(tmpC[i]))){
								position.add(i);
							}
						}
						
						ArrayList<String> combined= new ArrayList<String>();
						//controllo che position non sia vuoto
						if(!position.isEmpty()){
	
							String str_position= "";
							for(int j : position){
								
								str_position+= Integer.toString(j) + ",";
							}
							//mi crea le combinazioni separate da ,
							combined= miscellaneous.combine(str_position);
							
							if(!combined.isEmpty()){
								//se non è vuoto ciclo sull'array di combinazioni
								for(String combo : combined){
									//per ogni combinazione la scorro per trovare le posizioni da annullare
									char[] comboC= combo.toCharArray();
									//salvo le combinazioni in un array
									ArrayList<Integer> comboI= new ArrayList<Integer>();
									for(int i=0;i<comboC.length;i++){
										
										String str_combo= Character.toString(comboC[i]);
										if(!str_combo.equals(",")){
											
											comboI.add(Integer.valueOf(str_combo));
										}
									}
									
									//creo la nuova stringa da sostituire
									String strTmp= "";
									for(int i=0; i<tmpC.length; i++){
										
										if(!comboI.contains(i)){
											
											strTmp+= Character.toString(tmpC[i]);
										}
									}
									
									if(!strTmp.equals("") && !rightsideNew.contains(strTmp)){
										
										rightsideNew.add(strTmp);
									}
									
								}
							}
						}
						else if(!rightsideNew.contains(s) && !s.equals("e"))
							rightsideNew.add(s);
					}
				}
				//se S è nullable aggiungo S->e
				if(addSproduction && p.getLeftSide().equals(g.getS()))
					rightsideNew.add("e");
				
				p.setRightSide(rightsideNew);
				rightsideNew.clear();
			}
			System.out.println("Step 3 complete");
			
			//Step 4
			//elimina le e-production
			System.out.println("Step 4 complete");
			
			gg= new grammar(g.getVT(), g.getVN(), g.getS(), g.getAllProduction());
		}
		else {
			System.out.println("No e-production to remove");
			gg= g;
		}
		System.out.println("----------------------------------------------");
		System.out.println("End of eliminateEProduction procedure.");
		System.out.println("----------------------------------------------");
		System.out.println("Grammar after eliminateEProduction procedure.");
		gg.printItAll();
		
		return gg;
	}
	//-----------------------------------------------------------------------------------------------------------
	
	//elimina le unit production
	public static grammar eliminateUnitProduction(grammar g){

		System.out.println("----------------------------------------------");
		System.out.println("Starting of eliminateUnitProduction procedure.");
		System.out.println("----------------------------------------------");
		
		//popolo la coda di unit production
		FIFO fifo= new FIFO();
		ArrayList<production> productions= g.getAllProduction();
		utility.getUnitQueue(productions, fifo);
		if(fifo.isEmpty()) System.out.println("No unit production to remove.");
		//scorro la coda fin quando non è vuota
		while(!fifo.isEmpty()){
			
			fifo.printIt();
			String[] tmpString= fifo.popSplit();
			utility.replaceProduction(tmpString[0], tmpString[1], productions);
			
			//ripopolo la coda con le nuove unit production se ce ne sono
			utility.getUnitQueue(productions, fifo);
		}
		
		
		grammar gg= new grammar(g.getVT(), g.getVN(), g.getS(), g.getAllProduction());

		System.out.println("----------------------------------------------");
		System.out.println("End of eliminateUnitProduction procedure.");
		System.out.println("----------------------------------------------");
		System.out.println("Grammar after eliminateUnitProduction procedure.");
		gg.printItAll();
		System.out.println("----------------------------------------------");
		return gg;
	}
	//-----------------------------------------------------------------------------------------------------------
	
	/*
	 * una grammatica in Chomsky Normal Form è:
	 * A->BC
	 * A->a
	 * e se epsilon appartiene al linguaggio
	 * S->e
	 */
	//porta una grammatica in Chomsky Normal Form
	public static grammar chomskyNormalForm(grammar g){

		System.out.println("----------------------------------------------");
		System.out.println("Starting of CNF procedure");
		System.out.println("----------------------------------------------");
		
		if(!utility.isCNF(g.getAllProduction(), g.getVT())){
			//Step 1 semplifico la grammatica
				//elimino le e-production
				g= eliminateEpsilonProduction(g);
				
				//elimino le unit production
				g= eliminateUnitProduction(g);
			System.out.println("Step 1 complete, grammar simplified");
			//
			
			//Step 2 riduco l'ordine delle produzioni
			//creo l'insieme W a partire dall'insieme VN
			ArrayList<String> W= new ArrayList<String>();
			W.addAll(g.getVN());
			//creo l'insieme R a partire da P - {S->e}
			ArrayList<production> R= new ArrayList<production>();
			R.addAll(g.getAllProduction());
			boolean SEpresent= utility.removeSe(R, g.getS());
			System.out.println("removeSE complete");
			//riduco l'ordine della grammatica
			g= utility.reduceGrammarOrder(R, W, g.getVT());
			
			System.out.println("Step 2 complete, order decreased");
			//
			//Step 3 creo il nuovo VN e il nuovo P
			if(g != null)
				miscellaneous.removeStringFromArray(g.getVN());
			if(SEpresent) R.get(0).addProduction("e");
			System.out.println("Step 3 complete, new set of VN e P configured");
			//
		}
		else{
			System.out.println("Already in CNF.");
		}
			
	
		System.out.println("----------------------------------------------");
		System.out.println("End of CNF procedure");
		System.out.println("----------------------------------------------");
		System.out.println("Grammar after CNF procedure.");
		g.printItAll();
		return g;
	}
	//-----------------------------------------------------------------------------------------------------------

	public static boolean CYK(grammar g, String w){

		System.out.println("----------------------------------------------");
		System.out.println("Start of Coke Younger Kasami procedure");
		System.out.println("----------------------------------------------");
		
		//riduco la grammatica in Chomsky Normal Form
		g= chomskyNormalForm(g);
		
		System.out.println("Creating recognition matrix");
		String S= g.getS();
		
		matrix matrix= new matrix();
		matrix= utility.createRecognitionMatrix(g.getAllProduction(), w, matrix, g.getVT());
		
		//fine procedura per la creazione della recognition matrix
		System.out.println("Recognition matrix created: ");
		
		matrix.printIt();
		
		//controllo che l'assioma sia nella posizione <n-1, 0>
		int n= w.length();
		if(matrix.get(n-1, 0) != null && matrix.get(n-1, 0).contains(S)){

			System.out.println("----------------------------------------------");
			System.out.println("End of Coke Younger Kasami procedure");
			System.out.println("----------------------------------------------");
			return true;
		}

		System.out.println("----------------------------------------------");
		System.out.println("End of Coke Younger Kasami procedure");
		System.out.println("----------------------------------------------");
		
		return false;
	}
}
